#include "common.h"

vector<int> productExceptSelf(vector<int>& nums)
{
	int n = nums.size();
	vector<int> dp1(n + 1, 1);
	vector<int> dp2(n + 1, 1);
	vector<int> ans(n);
	for (int i = 0; i < n; i++)
	{
		dp1[i + 1] = dp1[i] * nums[i];
	}
	for (int i = n - 1; i >= 0; i--)
	{
		dp2[i] = dp2[i + 1] * nums[i];
	}
	for (int i = 0; i < n; i++)
	{
		ans[i] = dp1[i] * dp2[i + 1];
	}
	return ans;
}